package com.xiyou.week03.tree;

import java.util.*;

/**
 * 22. 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * @ClassName：GenerateParenthesis
 * @Author：西柚
 * @Date：2022/1/13 12:12 上午
 * @Versiion：1.0
 */
public class GenerateParenthesis {

    static Map<Integer, List<String>> store = new HashMap<>();

    /**
     * 输入：n = 3
     * 输出：["((()))","(()())","(())()","()(())","()()()"]
     * <p>
     * 输入：n = 1
     * 输出：["()"]
     *
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        if (n == 0) {
            ans.add("");
            return ans;
        }
        if (store.containsKey(n)) {
            // 记忆化
            return store.get(n);
        }

        for (int k = 1; k <= n; k++) {

            List<String> A = generateParenthesis(k - 1);
            List<String> B = generateParenthesis(n - k);
            // S=(A)B
            // 乘法原理
            for (String a : A) {
                for (String b : B) {
                    System.out.println("----------");
                    ans.add("(" + a + ")" + b);
                }
            }
        }

        store.put(n, new ArrayList<>(ans));
        System.out.println(store);
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }

}
